package com.lw.leetcode.binary.b;

/**
 * Created with IntelliJ IDEA.
 * 2513. 最小化两个数组中的最大值
 *
 * @author liw
 * @version 1.0
 * @date 2022/12/26 10:29
 */
public class MinimizeSet {


    public static void main(String[] args) {
        MinimizeSet test = new MinimizeSet();

        // 4
//        int divisor1 = 2;
//        int divisor2 = 7;
//        int uniqueCnt1 = 1;
//        int uniqueCnt2 = 3;

        // 3
//        int divisor1 = 3;
//        int divisor2 = 5;
//        int uniqueCnt1 = 2;
//        int uniqueCnt2 = 1;

        // 15
//        int divisor1 = 2;
//        int divisor2 = 4;
//        int uniqueCnt1 = 8;
//        int uniqueCnt2 = 2;

        // 39
//        int divisor1 = 5;
//        int divisor2 = 2;
//        int uniqueCnt1 = 2;
//        int uniqueCnt2 = 20;

        // 217679202
        int divisor1 = 92761;
        int divisor2 = 48337;
        int uniqueCnt1 = 208563424;
        int uniqueCnt2 = 9115778;

        int i = test.minimizeSet(divisor1, divisor2, uniqueCnt1, uniqueCnt2);
        System.out.println(i);
    }

    public int minimizeSet(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
        int st = uniqueCnt1 + uniqueCnt2;
        int end = Integer.MAX_VALUE;
        long all =  (long)divisor1 * divisor2 / find(divisor1, divisor2);
        while (st < end) {
            int m = st + ((end - st) >> 1);
            long c = m / all;
            long a = m / divisor1 - c;
            long b = m / divisor2 - c;
            long count = m - a - b - c;
            long t1 = Math.max(uniqueCnt1 - b, 0);
            long t2 = Math.max(uniqueCnt2 - a, 0);
            if (t1 + t2 <= count) {
                end = m;
            } else {
                st = m + 1;
            }
        }
        return st;
    }

    private int find(int a, int b) {
        if (b == 0) {
            return a;
        }
        return find(b, a % b);
    }

}
